﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace CSharpAlgorithm.Base
{
    /// <summary>
    /// 모든 노드 간의 최단거리를 구함
    /// 음의 가중치도 처리 가능
    /// O(V^3)
    /// </summary>
    class FloydWarshall
    {
        int[,] d;
        int v;
        public FloydWarshall(int v, int[,] d)
        {
            this.v = v;
            this.d = d;
        }
        public int[,] ShortestPath()
        {
            for (int k = 1; k <= v; k++)
            {
                for (int i = 1; i <= v; i++)
                {
                    for (int j = 1; j <= v; j++)
                    {

                        d[i, j] = Math.Min(d[i, j], 
                            (d[i, k] == int.MaxValue || d[k, j] == int.MaxValue) ? int.MaxValue : d[i, k] + d[k, j]);
                    }
                }
            }
            return d;
        }
    }
}
